#include <iostream>
#include <string>
#include <vector>

using namespace std;

int manacher(string &s) {
    int n = s.length();
    if (n < 2) {
        return n;
    }
    // 添加字符 #，使字符串的长度变为奇数
    string new_s = "#";
    for (int i = 0; i < n; i++) {
        new_s += s[i];
        new_s += "#";
    }
    n = new_s.length();

    vector<int> radius(n, 0); // 记录以每个字符为中心的最长回文半径
    int right = -1, center = -1; // 当前回文子串的最右端位置和对应的中心位置
    int max_len = 0;

    for (int i = 0; i < n; i++) {
        if (i < right) {
            radius[i] = min(radius[2 * center - i], right - i);
        }
        while (i - radius[i] - 1 >= 0 && i + radius[i] + 1 < n &&
               new_s[i - radius[i] - 1] == new_s[i + radius[i] + 1]) {
            radius[i]++;
        }
        if (i + radius[i] > right) {
            right = i + radius[i];
            center = i;
        }
        max_len = max(max_len, radius[i]);
    }
    return max_len;
}

int main() {
    string s = "babad";
    cout << manacher(s) << endl; // expected output: 3
    return 0;
}
/**
 * 马拉车算法（Manacher's Algorithm）是用于求解字符串最长回文子串长度的一种算法，时间复杂度为 $O(n)$，比传统的基于中心扩散或者动态规划的算法都要快。马拉车算法的基本思路是通过维护一个当前回文子串的最右端位置 $r$ 和对应的中心位置 $c$，在遍历字符串时尽可能利用已求得的回文信息，快速计算以每个字符为中心的最长回文半径。

相比于暴力枚举的算法，该实现方法有以下几个优势：

1. 在将原字符串转换成包含特殊字符 # 的新字符串后，可以确保每个回文串的长度都是奇数，不需要分情况讨论；同时，因为相邻字符之间有特殊字符 # 隔开，因此计算字符串的长度时只需要除以2即可。
2. 使用向右延伸和向左延伸两步同时进行的方法，而不是像暴力枚举算法那样一次只向一个方向延伸，能够使计算速度更快。
3. 马拉车算法的时间复杂度为 $O(n)$，比暴力枚举的算法的时间复杂度 $O(n^3)$ 要快很多。

*/